﻿#define _CRT_SECURE_NO_WARNINGS

/* 题目要求条件*/

class Solution
{
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
public:
	vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
	{
		int m = mat.size(), n = mat[0].size();
		// dist[i][j] == -1 表⽰：没有搜索过
		// dist[i][j] != -1 表⽰：最短距离
		vector<vector<int>> dist(m, vector<int>(n, -1));
		queue<pair<int, int>> q;
		// 1. 把所有的源点加⼊到队列中
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				if (mat[i][j] == 0)
				{
					q.push({ i, j });
					dist[i][j] = 0;
				}
		// 2. ⼀层⼀层的往外扩
		while (q.size())
		{
			auto [a, b] = q.front(); q.pop();
			for (int i = 0; i < 4; i++)
			{
				int x = a + dx[i], y = b + dy[i];
				if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
				{
					dist[x][y] = dist[a][b] + 1;
					q.push({ x, y });
				}
			}
		}
		return dist;
	}
};

